{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Best Meeting Point"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #math #matrix #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #数学 #矩阵 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minTotalDistance"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最佳的碰头地点"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个&nbsp;<code>m x n</code>&nbsp;&nbsp;的二进制网格&nbsp;<code>grid</code>&nbsp;，其中 <code>1</code> 表示某个朋友的家所处的位置。返回 <em>最小的 <strong>总行走距离</strong></em> 。</p>\n",
    "\n",
    "<p><strong>总行走距离</strong> 是朋友们家到碰头地点的距离之和。</p>\n",
    "\n",
    "<p>我们将使用&nbsp;<a href=\"https://baike.baidu.com/item/%E6%9B%BC%E5%93%88%E9%A1%BF%E8%B7%9D%E7%A6%BB\" target=\"_blank\">曼哈顿距离</a>&nbsp;来计算，其中&nbsp;<code>distance(p1, p2) = |p2.x - p1.x| + |p2.y - p1.y|</code>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2021/03/14/meetingpoint-grid.jpg\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> grid = [[1,0,0,0,1],[0,0,0,0,0],[0,0,1,0,0]]\n",
    "<strong>输出: </strong>6 <strong>\n",
    "解释: </strong>给定的三个人分别住在<code>(0,0)，</code><code>(0,4) </code>和 <code>(2,2)</code>:\n",
    "&nbsp;    <code>(0,2)</code> 是一个最佳的碰面点，其总行走距离为 2 + 2 + 2 = 6，最小，因此返回 6。</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> grid = [[1,1]]\n",
    "<strong>输出:</strong> 1</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == grid.length</code></li>\n",
    "\t<li><code>n == grid[i].length</code></li>\n",
    "\t<li><code>1 &lt;= m, n &lt;= 200</code></li>\n",
    "\t<li><code>grid[i][j] ==</code>&nbsp;<code>0</code>&nbsp;or&nbsp;<code>1</code>.</li>\n",
    "\t<li><code>grid</code>&nbsp;中 <strong>至少</strong> 有两个朋友</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [best-meeting-point](https://leetcode.cn/problems/best-meeting-point/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [best-meeting-point](https://leetcode.cn/problems/best-meeting-point/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,0,0,0,1],[0,0,0,0,0],[0,0,1,0,0]]', '[[1,1]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTotalDistance(self, grid: List[List[int]]) -> int:\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        row = [0 for _ in range(n)]\n",
    "        col = [0 for _ in range(m)]\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid[i][j]:\n",
    "                    row[i] += 1\n",
    "                    col[j] += 1\n",
    "        ans = inf\n",
    "        # print(row, col)\n",
    "        def get(i, j):\n",
    "            # 此时将集合地定到i,j位置\n",
    "            cur = 0\n",
    "            for x in range(n):\n",
    "                cur += abs(x - i) * row[x]\n",
    "            for y in range(m):\n",
    "                cur += abs(y - j) * col[y]\n",
    "            return cur\n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                ans = min(ans, get(i, j))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTotalDistance(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        elements = []\n",
    "        n,m = len(grid),len(grid[0])\n",
    "        rows = collections.defaultdict(int)\n",
    "        cols = collections.defaultdict(int)\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid[i][j]>0:\n",
    "                    rows[i] += 1\n",
    "                    cols[j] += 1\n",
    "        \n",
    "        min_row_dist = float(\"inf\")\n",
    "        for i in range(n):\n",
    "            dist = 0 \n",
    "            for x in rows:\n",
    "                dist += abs(x-i)*rows[x]\n",
    "            min_row_dist = min(min_row_dist, dist)\n",
    "        \n",
    "        col_dist = float(\"inf\")\n",
    "        for j in range(m):\n",
    "            dist = 0 \n",
    "            for x in cols:\n",
    "                dist += abs(x-j)*cols[x]\n",
    "            col_dist = min(col_dist, dist)\n",
    "        return col_dist+min_row_dist\n",
    "\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTotalDistance(self, grid: List[List[int]]) -> int:\n",
    "        m, n =len(grid), len(grid[0])\n",
    "        v1 = [0] * m \n",
    "        v2 = [0] * n \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                v1[i] += grid[i][j]\n",
    "                v2[j] += grid[i][j]\n",
    "\n",
    "        x1, x2 = 0, 0\n",
    "        s1, s2 = sum(v1), sum(v2)\n",
    "        t1, t2 = 0, 0\n",
    "        while x1 < m:\n",
    "            t1 += v1[x1]\n",
    "            if t1 >= (s1+1)//2:\n",
    "                break \n",
    "            x1+=1\n",
    "        while x2 < n:\n",
    "            t2 += v2[x2]\n",
    "            if t2 >= (s2+1)//2:\n",
    "                break \n",
    "            x2 += 1\n",
    "        #print(x1,x2)\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]:\n",
    "                    ans += abs(x1 - i) + abs(x2 - j) \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTotalDistance(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        row = [0] * m \n",
    "        col = [0] * n \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]:\n",
    "                    col[j] += 1\n",
    "                    row[i] += 1\n",
    "        \n",
    "        x, y = 0, 0\n",
    "        max1, max2 = float('inf'), float('inf')\n",
    "\n",
    "        for i in range(n):\n",
    "            sum_dist = 0\n",
    "            for j in range(n):\n",
    "                sum_dist += abs(i - j) * col[j] \n",
    "            if max2 > sum_dist:\n",
    "                max2 = sum_dist \n",
    "                y = i \n",
    "        for i in range(m):\n",
    "            sum_dist = 0\n",
    "            for j in range(m):\n",
    "                sum_dist += abs(i - j) * row[j]\n",
    "            if max1 > sum_dist:\n",
    "                max1 = sum_dist \n",
    "                x = i \n",
    "        \n",
    "        return max1 + max2 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTotalDistance(self, grid: List[List[int]]) -> int:\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        row = [0 for _ in range(n)]\n",
    "        col = [0 for _ in range(m)]\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid[i][j]:\n",
    "                    row[i] += 1\n",
    "                    col[j] += 1\n",
    "        ans = inf\n",
    "        def get(i, j):\n",
    "            # 此时将集合地定到i,j位置\n",
    "            cur = 0\n",
    "            for x in range(n):\n",
    "                cur += abs(x - i) * row[x]\n",
    "            for y in range(m):\n",
    "                cur += abs(y - j) * col[y]\n",
    "            return cur\n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                cur = get(i, j)\n",
    "                ans = cur if cur < ans else ans\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTotalDistance(self, grid: List[List[int]]) -> int:\n",
    "        rowCnts = [0] * len(grid)\n",
    "        colCnts = [0] * len(grid[0])\n",
    "        fCnt = 0\n",
    "        for rowIdx in range(len(grid)):\n",
    "            for colIdx in range(len(grid[0])):\n",
    "                if grid[rowIdx][colIdx] == 1:\n",
    "                    fCnt += 1\n",
    "                    rowCnts[rowIdx] += 1\n",
    "                    colCnts[colIdx] += 1\n",
    "        \n",
    "        # find best rowIdx\n",
    "        cnt = 0\n",
    "        for rowIdx in range(len(grid)):\n",
    "            for _i in range(rowCnts[rowIdx]):\n",
    "                cnt += 1\n",
    "                if cnt == (fCnt + 1) // 2:\n",
    "                    bestRowIdx = rowIdx\n",
    "                    break\n",
    "        # find best colIdx\n",
    "        cnt = 0\n",
    "        for colIdx in range(len(grid[0])):\n",
    "            for _i in range(colCnts[colIdx]):\n",
    "                cnt += 1\n",
    "                if cnt == (fCnt + 1) // 2:\n",
    "                    bestColIdx = colIdx\n",
    "                    break\n",
    "\n",
    "        # cal dist\n",
    "        dist = 0\n",
    "        for rowIdx in range(len(grid)):\n",
    "            dist += abs(rowIdx - bestRowIdx) * rowCnts[rowIdx]\n",
    "        for colIdx in range(len(grid[0])):\n",
    "            dist += abs(colIdx - bestColIdx) * colCnts[colIdx]\n",
    "        return dist\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTotalDistance(self, grid: List[List[int]]) -> int:\n",
    "        Row = len(grid)\n",
    "        Col = len(grid[0])\n",
    "\n",
    "        rs = []\n",
    "        cs = []\n",
    "        for r in range(Row):\n",
    "            for c in range(Col):\n",
    "                if grid[r][c] == 1:\n",
    "                    rs.append(r)\n",
    "                    cs.append(c)\n",
    "        \n",
    "        rs.sort()\n",
    "        cs.sort()\n",
    "        rn = len(rs)\n",
    "        cn = len(cs)\n",
    "        r_mid = rs[rn//2]\n",
    "        c_mid = cs[cn//2]\n",
    "\n",
    "        res = 0\n",
    "        for r in range(Row):\n",
    "            for c in range(Col):\n",
    "                if grid[r][c] == 1:\n",
    "                    res += abs(r - r_mid) + abs(c - c_mid)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTotalDistance(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "\n",
    "        arr = []\n",
    "        x_, y_ = [], []\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    x_.append(i)\n",
    "                    y_.append(j)\n",
    "\n",
    "        def mids(arr: List[int]) -> int:\n",
    "            arr.sort()\n",
    "            k = len(arr)\n",
    "\n",
    "            res = 0\n",
    "            v = arr[k // 2]\n",
    "            for o in arr:\n",
    "                res += abs(o - v)\n",
    "\n",
    "            return res\n",
    "\n",
    "        ans = mids(x_) + mids(y_)\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTotalDistance(self, grid: List[List[int]]) -> int:\n",
    "        m,n =len(grid),len(grid[0])\n",
    "        ls1=[]\n",
    "        ls2=[]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==1:\n",
    "                    ls1.append(i)\n",
    "                    ls2.append(j)\n",
    "        ls1.sort()\n",
    "        ls2.sort()\n",
    "        m1,m2=ls1[len(ls1)//2],ls2[len(ls2)//2]\n",
    "        ans=0\n",
    "        #print(ls1,ls2,m1,m2)\n",
    "        for i in ls1:\n",
    "            ans+=abs(m1-i)\n",
    "        for j in ls2:\n",
    "            ans+=abs(m2-j)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTotalDistance(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        m = len(grid[0])\n",
    "        X = []\n",
    "        Y = []\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if(grid[i][j]==1): \n",
    "                    X.append(i)\n",
    "                    Y.append(j)\n",
    "        X.sort()\n",
    "        Y.sort()\n",
    "        n= len(X)\n",
    "        m = n//2\n",
    "        r =0\n",
    "        for i in range(m):\n",
    "            r+=(X[n-i-1]-X[i])+(Y[n-i-1]-Y[i])\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTotalDistance(self, grid: List[List[int]]) -> int:\n",
    "        rows, cols = [], []\n",
    "        \n",
    "        # Collect the rows and columns where houses are located\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j] == 1:\n",
    "                    rows.append(i)\n",
    "                    cols.append(j)\n",
    "        \n",
    "        rows.sort()\n",
    "        cols.sort()\n",
    "        \n",
    "        # Find the median of rows and cols as the best meeting point\n",
    "        row_mid = rows[len(rows) // 2]\n",
    "        col_mid = cols[len(cols) // 2]\n",
    "        \n",
    "        # Calculate the total distance using Manhattan distance\n",
    "        return sum(abs(row - row_mid) for row in rows) + sum(abs(col - col_mid) for col in cols)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTotalDistance(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        rs = [i for i in range(m) for j in range(n) if grid[i][j] == 1]\n",
    "        cs = [j for j in range(n) for i in range(m) if grid[i][j] == 1]\n",
    "        mr = rs[len(rs)//2]\n",
    "        mc = cs[len(cs)//2]\n",
    "        distance = 0\n",
    "        for r in rs:\n",
    "            distance += abs(r - mr)\n",
    "\n",
    "        for c in cs:\n",
    "            distance += abs(c - mc)\n",
    "\n",
    "        return distance"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTotalDistance(self, grid: List[List[int]]) -> int:\n",
    "        row,col = [],[]\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==1:\n",
    "                    row.append(i)\n",
    "                    col.append(j)\n",
    "        row.sort()\n",
    "        col.sort()\n",
    "        xm,xy = row[len(row)//2],col[len(col)//2]\n",
    "        distance = 0\n",
    "        for i in range(len(row)):\n",
    "            distance += abs(xm-row[i])+abs(xy-col[i])\n",
    "        return distance\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTotalDistance(self, grid: List[List[int]]) -> int:\n",
    "        rows, cols = [], []\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]:\n",
    "                    rows.append(i)\n",
    "                    cols.append(j)\n",
    "\n",
    "        def find_middle(L):\n",
    "            ln = len(L)\n",
    "            L.sort()\n",
    "            return L[ln // 2]\n",
    "\n",
    "        r, c = find_middle(rows), find_middle(cols)\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]:\n",
    "                    ans += abs(r - i) + abs(c - j)\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTotalDistance(self, grid: List[List[int]]) -> int:\n",
    "        xs, ys = [], []\n",
    "        for x, row in enumerate(grid):\n",
    "            for y, c in enumerate(row):\n",
    "                if c:\n",
    "                    xs.append(x)\n",
    "                    ys.append(y)\n",
    "        xs.sort()\n",
    "        ys.sort()\n",
    "        ans = 0\n",
    "        i = 0\n",
    "        while i < len(xs) - 1 - i:\n",
    "            ans += xs[-1-i] - xs[i]\n",
    "            i += 1\n",
    "        i = 0\n",
    "        while i < len(ys) - 1 - i:\n",
    "            ans += ys[-1-i] - ys[i]\n",
    "            i += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTotalDistance(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        rows = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    rows.append(i) # i row, i row ...\n",
    "        row_median = rows[len(rows)//2]\n",
    "\n",
    "        cols = []\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid[j][i] == 1:\n",
    "                    cols.append(i)\n",
    "        col_median = cols[len(cols)//2]\n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    res += abs(i - row_median) + abs(j - col_median)\n",
    "        return res\n",
    "   \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTotalDistance(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        rs = [i for i in range(m) for j in range(n) if grid[i][j] == 1]\n",
    "        cs = [j for j in range(n) for i in range(m) if grid[i][j] == 1]\n",
    "        mr = rs[len(rs)//2]\n",
    "        mc = cs[len(cs)//2]\n",
    "        return sum(abs(r - mr) for r in rs) + sum(abs(c - mc) for c in cs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTotalDistance(self, grid: List[List[int]]) -> int:\n",
    "        Row = len(grid)\n",
    "        Col = len(grid[0])\n",
    "\n",
    "        rs = []\n",
    "        cs = []\n",
    "        for r in range(Row):\n",
    "            for c in range(Col):\n",
    "                if grid[r][c] == 1:\n",
    "                    rs.append(r)\n",
    "                    cs.append(c)\n",
    "        \n",
    "        rs.sort()\n",
    "        cs.sort()\n",
    "        rn = len(rs)\n",
    "        cn = len(cs)\n",
    "        r_mid = rs[rn//2]\n",
    "        c_mid = cs[cn//2]\n",
    "\n",
    "        res = 0\n",
    "        for r in range(Row):\n",
    "            for c in range(Col):\n",
    "                if grid[r][c] == 1:\n",
    "                    res += abs(r - r_mid) + abs(c - c_mid)\n",
    "        return res\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTotalDistance(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        \n",
    "        # step 1: find row_median\n",
    "        rows = []\n",
    "        for i in range(m):   # 这样遍历完了之后row就已经天然sort好了，后面求meadian就很简单了\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    rows.append(i)\n",
    "        row_median = rows[len(rows) // 2]\n",
    "        \n",
    "        # step 2: find col_median\n",
    "        cols = []\n",
    "        for j in range(n):  # 这样遍历完了之后col就已经天然sort好了，后面求meadian就很简单了\n",
    "            for i in range(m):\n",
    "                if grid[i][j] == 1:\n",
    "                    cols.append(j)\n",
    "        col_median = cols[len(cols) // 2]\n",
    "        \n",
    "        # step 3: the min total distance is sum of every house to (row_median, col_median)\n",
    "        dist = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    dist += abs(i - row_median) + abs(j - col_median)\n",
    "        return dist\n",
    "\"\"\"\n",
    "这道题让我们求最佳的开会地点，该地点需要到每个为1的点的曼哈顿距离之和最小，题目中给了提示，让从一维的情况来分析，先看一维时有两个点A和B的情况,\n",
    "\n",
    "______A_____P_______B_______\n",
    "\n",
    "可以发现，只要开会为位置P在 [A, B] 区间内，不管在哪，距离之和都是A和B之间的距离，如果P不在 [A, B] 之间，那么距离之和就会大于A和B之间的距离，现在再加两个点C和D：\n",
    "\n",
    "______C_____A_____P_______B______D______\n",
    "\n",
    "通过分析可以得出，P点的最佳位置就是在 [A, B] 区间内.\n",
    "\n",
    "如果加入很多点，我们选择最佳的点是最小区间[A, B]之间的点，也就是[median - 1, median + 1]之间选一个点，\n",
    "\n",
    "这就是为什么我们需要选择median了\n",
    "\"\"\"\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\"\"\"\n",
    "It all about finding median, very similar with 462. Minimum Moves to Equal Array Elements II.\n",
    "注意这里千万不要求mean, 而是求median\n",
    "Median minimizes the absolute distance of points. \n",
    "Mean minimizes the squared distance from points.\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minTotalDistance(self, grid: List[List[int]]) -> int:\r\n",
    "        Row = len(grid)\r\n",
    "        Col = len(grid[0])\r\n",
    "\r\n",
    "        rs = []\r\n",
    "        cs = []\r\n",
    "        for r in range(Row):\r\n",
    "            for c in range(Col):\r\n",
    "                if grid[r][c] == 1:\r\n",
    "                    rs.append(r)\r\n",
    "                    cs.append(c)\r\n",
    "        \r\n",
    "        rs.sort()\r\n",
    "        cs.sort()\r\n",
    "        rn = len(rs)\r\n",
    "        cn = len(cs)\r\n",
    "        r_mid = rs[rn//2]\r\n",
    "        c_mid = cs[cn//2]\r\n",
    "\r\n",
    "        res = 0\r\n",
    "        for r in range(Row):\r\n",
    "            for c in range(Col):\r\n",
    "                if grid[r][c] == 1:\r\n",
    "                    res += abs(r - r_mid) + abs(c - c_mid)\r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTotalDistance(self, grid: List[List[int]]) -> int:\n",
    "        Row = len(grid)\n",
    "        Col = len(grid[0])\n",
    "\n",
    "        rs = []\n",
    "        cs = []\n",
    "        for r in range(Row):\n",
    "            for c in range(Col):\n",
    "                if grid[r][c] == 1:\n",
    "                    rs.append(r)\n",
    "                    cs.append(c)\n",
    "        \n",
    "        rs.sort()\n",
    "        cs.sort()\n",
    "        rn = len(rs)\n",
    "        cn = len(cs)\n",
    "        r_mid = rs[rn//2]\n",
    "        c_mid = cs[cn//2]\n",
    "\n",
    "        res = 0\n",
    "        for r in range(Row):\n",
    "            for c in range(Col):\n",
    "                if grid[r][c] == 1:\n",
    "                    res += abs(r - r_mid) + abs(c - c_mid)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from typing import List\n",
    "from collections import defaultdict, deque\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minTotalDistance(self, grid: List[List[int]]) -> int:\n",
    "        \"\"\"\n",
    "\n",
    "        :param grid:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        xidx = []\n",
    "        yidx = []\n",
    "        for k,v in enumerate(grid):\n",
    "            for k2, v2 in enumerate(v):\n",
    "                if v2 == 1:\n",
    "                    xidx.append(k)\n",
    "                    yidx.append(k2)\n",
    "\n",
    "        def get_ans(ll):\n",
    "            if len(ll) %2 == 0:\n",
    "                return ll[len(ll)//2-1]\n",
    "            return ll[len(ll)//2]\n",
    "        xidx.sort()\n",
    "        yidx.sort()\n",
    "        ans = 0\n",
    "        idx1 = get_ans(xidx)\n",
    "        idx2 = get_ans(yidx)\n",
    "        for i in xidx:\n",
    "            ans += abs(i - idx1)\n",
    "        for i in yidx:\n",
    "            ans += abs(i - idx2)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTotalDistance(self, grid: List[List[int]]) -> int:\n",
    "        l1,l2=[],[]\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j]==1:\n",
    "                    l1.append(i)\n",
    "                    l2.append(j)\n",
    "        l1.sort()\n",
    "        l2.sort()\n",
    "        res1=sum(l1[len(l1)//2:])-sum(l1[:len(l1)//2]) if len(l1)%2==0 else sum(l1[len(l1)//2+1:])-sum(l1[:len(l1)//2])\n",
    "        res2=sum(l2[len(l2)//2:])-sum(l2[:len(l2)//2]) if len(l2)%2==0 else sum(l2[len(l2)//2+1:])-sum(l2[:len(l2)//2])\n",
    "        return res1+res2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTotalDistance(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        rows = []\n",
    "        cols = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    rows.append(i)\n",
    "        for j in range(n):\n",
    "            for i in range(m):\n",
    "                if grid[i][j] == 1:\n",
    "                    cols.append(j) \n",
    "        return sum(abs(r - rows[len(rows) // 2]) for r in rows) + sum(abs(c - cols[len(cols) // 2]) for c in cols)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTotalDistance(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        \n",
    "        # step 1: find row_median\n",
    "        rows = []\n",
    "        for i in range(m):   # 这样遍历完了之后row就已经天然sort好了，后面求meadian就很简单了\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    rows.append(i)\n",
    "        row_median = rows[len(rows) // 2]\n",
    "        \n",
    "        # step 2: find col_median\n",
    "        cols = []\n",
    "        for j in range(n):  # 这样遍历完了之后col就已经天然sort好了，后面求meadian就很简单了\n",
    "            for i in range(m):\n",
    "                if grid[i][j] == 1:\n",
    "                    cols.append(j)\n",
    "        col_median = cols[len(cols) // 2]\n",
    "        \n",
    "        # step 3: the min total distance is sum of every house to (row_median, col_median)\n",
    "        dist = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    dist += abs(i - row_median) + abs(j - col_median)\n",
    "        return dist\n",
    "\"\"\"\n",
    "这道题让我们求最佳的开会地点，该地点需要到每个为1的点的曼哈顿距离之和最小，题目中给了提示，让从一维的情况来分析，先看一维时有两个点A和B的情况,\n",
    "\n",
    "______A_____P_______B_______\n",
    "\n",
    "可以发现，只要开会为位置P在 [A, B] 区间内，不管在哪，距离之和都是A和B之间的距离，如果P不在 [A, B] 之间，那么距离之和就会大于A和B之间的距离，现在再加两个点C和D：\n",
    "\n",
    "______C_____A_____P_______B______D______\n",
    "\n",
    "通过分析可以得出，P点的最佳位置就是在 [A, B] 区间内.\n",
    "\n",
    "如果加入很多点，我们选择最佳的点是最小区间[A, B]之间的点，也就是[median - 1, median + 1]之间选一个点，\n",
    "\n",
    "这就是为什么我们需要选择median了\n",
    "\"\"\"\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\"\"\"\n",
    "It all about finding median, very similar with 462. Minimum Moves to Equal Array Elements II.\n",
    "注意这里千万不要求mean, 而是求median\n",
    "Median minimizes the absolute distance of points. \n",
    "Mean minimizes the squared distance from points.\n",
    "\"\"\"\n",
    "\"\"\"\n",
    "Collect all row indices of all houses.\n",
    "Collect all col indices of all houses.\n",
    "Calculate min distance when put the meeting point among houses by rows -> The meeting point row idx must be the median between row ids.\n",
    "Calculate min distance when put the meeting points among houses by cols -> The meeting point col idx must be the median between col ids.\n",
    "To prove why median work, can check this problem 1478. Allocate Mailboxes.\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def minTotalDistance(self, grid: List[List[int]]) -> int:\n",
    "        num_friends = 0\n",
    "        xs = []\n",
    "        ys = []\n",
    "        sum_distance = 0\n",
    "\n",
    "\n",
    "        for row in range(len(grid)):\n",
    "            for col in range(len(grid[row])):\n",
    "                if grid[row][col] == 1:\n",
    "                    xs.append(col)\n",
    "                    ys.append(row)\n",
    "        \n",
    "\n",
    "        xs = sorted(xs)\n",
    "        ys = sorted(ys)\n",
    "        n  = len(xs)\n",
    "        x = xs[n//2]\n",
    "        y = ys[n//2]\n",
    "\n",
    "        return sum([abs(_-x) for _ in xs]) + sum([abs(_-y) for _ in ys]) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTotalDistance(self, grid: List[List[int]]) -> int:\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        xp=[]\n",
    "        yp=[]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==1:\n",
    "                    xp.append(i)\n",
    "                    yp.append(j)\n",
    "\n",
    "        nx=len(xp)\n",
    "        ny=len(yp)\n",
    "        print(xp)\n",
    "        print(yp)\n",
    "        xp.sort()\n",
    "        yp.sort()\n",
    "        x=xp[nx//2]\n",
    "        y=yp[ny//2]\n",
    "  \n",
    "        res=0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==1:\n",
    "                    res+=abs(i-x)+abs(j-y)\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTotalDistance(self, grid: List[List[int]]) -> int:\n",
    "      # 两个坐标中位数\n",
    "      m,n = len(grid),len(grid[0])\n",
    "      posi = []\n",
    "\n",
    "      hx ,hy = [],[]\n",
    "      for i in range(m):\n",
    "        for j in range(n):\n",
    "          if grid[i][j] == 1:\n",
    "            posi.append((i,j))\n",
    "      \n",
    "      M = len(posi)\n",
    "      for x,y in posi:\n",
    "        heappush(hx,x)\n",
    "        heappush(hy,y)\n",
    "        if len(hx)>1+M//2:\n",
    "          heappop(hx)\n",
    "        if len(hy)>1+M//2:\n",
    "          heappop(hy)\n",
    "      \n",
    "      midx,midy = hx[0],hy[0]\n",
    "      ans = 0\n",
    "      for x, y in posi:\n",
    "        ans += abs(x-midx) + abs(y-midy)\n",
    "      return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTotalDistance(self, grid: List[List[int]]) -> int:\n",
    "        \"\"\"\n",
    "        思路一：记录能到达当前0节点的所有1的个数，并累加距离每个1的距离。当前0节点1能到达的个数和全部1的个数相等，那么就下这个前提下求最小的距离累加和。注意：这个思路在本题中会因为大量全1的测试用例超时。\n",
    "        思路二：grid只要1和0，汇合点可能是1，也可能是0，所以只要找到所有x和y坐标的中位数坐标，同各个1坐标的曼哈段距离，求最小的就是答案\n",
    "        \"\"\"\n",
    "        def find_mid(lst):\n",
    "            lst.sort()\n",
    "            return lst[len(lst) // 2]\n",
    "\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        x_lst = []\n",
    "        y_lst = []\n",
    "        coordinate = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    x_lst.append(i)\n",
    "                    y_lst.append(j)\n",
    "                    coordinate.append((i, j))\n",
    "\n",
    "        x = find_mid(x_lst)\n",
    "        y = find_mid(y_lst)\n",
    "        res = 0\n",
    "        for i, j in coordinate:\n",
    "            res += (abs(x - i) + abs(y - j))\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTotalDistance(self, grid: List[List[int]]) -> int:\n",
    "        \"\"\"\n",
    "        思路一：记录能到达当前0节点的所有1的个数，并累加距离每个1的距离。当前0节点1能到达的个数和全部1的个数相等，那么就下这个前提下求最小的距离累加和。注意：这个思路在本题中会因为大量全1的测试用例超时。\n",
    "        思路二：grid只要1和0，汇合点可能是1，也可能是0，所以只要找到所有x和y坐标的中位数坐标，同各个1坐标的曼哈段距离，求最小的就是答案\n",
    "        \"\"\"\n",
    "        def find_mid(lst):\n",
    "            lst.sort()\n",
    "            return lst[len(lst) // 2]\n",
    "\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        x_lst = []\n",
    "        y_lst = []\n",
    "        coordinate = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    x_lst.append(i)\n",
    "                    y_lst.append(j)\n",
    "                    coordinate.append((i, j))\n",
    "\n",
    "        x = find_mid(x_lst)\n",
    "        y = find_mid(y_lst)\n",
    "        res = 0\n",
    "        for i, j in coordinate:\n",
    "            res += (abs(x - i) + abs(y - j))\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTotalDistance(self, grid: List[List[int]]) -> int:\n",
    "        \"\"\"\n",
    "        思路一：记录能到达当前0节点的所有1的个数，并累加距离每个1的距离。当前0节点1能到达的个数和全部1的个数相等，那么就下这个前提下求最小的距离累加和。注意：这个思路在本题中会因为大量全1的测试用例超时。\n",
    "        思路二：grid只要1和0，汇合点可能是1，也可能是0，所以只要找到所有x和y坐标的中位数坐标，同各个1坐标的曼哈段距离，求最小的就是答案\n",
    "        \"\"\"\n",
    "        def find_mid(lst):\n",
    "            lst.sort()\n",
    "            return lst[len(lst) // 2]\n",
    "\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        x = []\n",
    "        y = []\n",
    "        coordinate = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    x.append(i)\n",
    "                    y.append(j)\n",
    "                    coordinate.append((i, j))\n",
    "\n",
    "        x = find_mid(x)\n",
    "        y = find_mid(y)\n",
    "        res = 0\n",
    "        for i, j in coordinate:\n",
    "            res += (abs(x - i) + abs(y - j))\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTotalDistance(self, grid: List[List[int]]) -> int:\n",
    "        \"\"\"\n",
    "        思路一：记录能到达当前0节点的所有1的个数，并累加距离每个1的距离。当前0节点1能到达的个数和全部1的个数相等，那么就下这个前提下求最小的距离累加和。注意：这个思路在本题中会因为大量全1的测试用例超时。\n",
    "        思路二：grid只要1和0，汇合点可能是1，也可能是0，所以只要找到所有x和y坐标的中位数坐标，同各个1坐标的曼哈段距离，求最小的就是答案\n",
    "        \"\"\"\n",
    "        def find_mid(lst):\n",
    "            lst.sort()\n",
    "            return lst[len(lst) // 2]\n",
    "\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        x_lst = []\n",
    "        y_lst = []\n",
    "        coordinate = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    x_lst.append(i)\n",
    "                    y_lst.append(j)\n",
    "                    coordinate.append((i, j))\n",
    "\n",
    "        x = find_mid(x_lst)\n",
    "        y = find_mid(y_lst)\n",
    "        res = 0\n",
    "        for i, j in coordinate:\n",
    "            res += (abs(x - i) + abs(y - j))\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTotalDistance(self, grid: List[List[int]]) -> int:\n",
    "        \"\"\"\n",
    "        思路一：记录能到达当前0节点的所有1的个数，并累加距离每个1的距离。当前0节点1能到达的个数和全部1的个数相等，那么就下这个前提下求最小的距离累加和。注意：这个思路在本题中会因为大量全1的测试用例超时。\n",
    "        思路二：grid只要1和0，汇合点可能是1，也可能是0，所以只要找到所有x和y坐标的中位数坐标，同各个1坐标的曼哈段距离，求最小的就是答案\n",
    "        \"\"\"\n",
    "        def find_mid(lst):\n",
    "            lst.sort()\n",
    "            return lst[len(lst) // 2]\n",
    "\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        x = []\n",
    "        y = []\n",
    "        coordinate = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    x.append(i)\n",
    "                    y.append(j)\n",
    "                    coordinate.append((i, j))\n",
    "\n",
    "        x = find_mid(x)\n",
    "        y = find_mid(y)\n",
    "        res = 0\n",
    "        for i, j in coordinate:\n",
    "            res += (abs(x - i) + abs(y - j))\n",
    "        return res\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
